{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Detonate the Maximum Bombs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumDetonation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #引爆最多的炸弹"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个炸弹列表。一个炸弹的 <strong>爆炸范围</strong>&nbsp;定义为以炸弹为圆心的一个圆。</p>\n",
    "\n",
    "<p>炸弹用一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>bombs</code>&nbsp;表示，其中&nbsp;<code>bombs[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code>&nbsp;。<code>x<sub>i</sub></code> 和&nbsp;<code>y<sub>i</sub></code>&nbsp;表示第 <code>i</code>&nbsp;个炸弹的 X 和 Y 坐标，<code>r<sub>i</sub></code>&nbsp;表示爆炸范围的 <strong>半径</strong>&nbsp;。</p>\n",
    "\n",
    "<p>你需要选择引爆 <strong>一个&nbsp;</strong>炸弹。当这个炸弹被引爆时，<strong>所有</strong> 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。</p>\n",
    "\n",
    "<p>给你数组&nbsp;<code>bombs</code>&nbsp;，请你返回在引爆&nbsp;<strong>一个</strong>&nbsp;炸弹的前提下，<strong>最多</strong>&nbsp;能引爆的炸弹数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-3.png\" style=\"width: 300px; height: 300px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>bombs = [[2,1,3],[6,1,4]]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "上图展示了 2 个炸弹的位置和爆炸范围。\n",
    "如果我们引爆左边的炸弹，右边的炸弹不会被影响。\n",
    "但如果我们引爆右边的炸弹，两个炸弹都会爆炸。\n",
    "所以最多能引爆的炸弹数目是 max(1, 2) = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-2.png\" style=\"width: 300px; height: 300px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>bombs = [[1,1,5],[10,10,5]]\n",
    "<b>输出：</b>1\n",
    "<strong>解释：\n",
    "</strong>引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/07/desmos-eg1.png\" style=\"width: 300px; height: 300px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>\n",
    "最佳引爆炸弹为炸弹 0 ，因为：\n",
    "- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。\n",
    "- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。\n",
    "- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。\n",
    "所以总共有 5 个炸弹被引爆。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= bombs.length&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>bombs[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [detonate-the-maximum-bombs](https://leetcode.cn/problems/detonate-the-maximum-bombs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [detonate-the-maximum-bombs](https://leetcode.cn/problems/detonate-the-maximum-bombs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1,3],[6,1,4]]', '[[1,1,5],[10,10,5]]', '[[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs):\n",
    "        n, max_bombs, graph = len(bombs), 0, defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if bombs[i][2] ** 2 >= (bombs[i][0] - bombs[j][0]) ** 2 + (bombs[i][1] - bombs[j][1]) ** 2:\n",
    "                    graph[i] += [j]\n",
    "\n",
    "        def dfs(node, visited):\n",
    "            for child in graph[node]:\n",
    "                if child not in visited:\n",
    "                    visited.add(child)\n",
    "                    dfs(child, visited)\n",
    "\n",
    "        for i in range(n):\n",
    "            visited = set([i])\n",
    "            dfs(i, visited)\n",
    "            max_bombs = max(max_bombs, len(visited))\n",
    "\n",
    "        return max_bombs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        num = len(bombs)\n",
    "        d = defaultdict(list)\n",
    "        for i in range(num):\n",
    "            for j in range(num):\n",
    "                if i != j and (bombs[i][0] - bombs[j][0]) **2 + (bombs[i][1] - bombs[j][1])** 2 <= bombs[i][2] ** 2:\n",
    "                    d[i].append(j)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(num):\n",
    "            visited = [False] * num\n",
    "            q = [i]\n",
    "            cnt = 1\n",
    "            visited[i] = True\n",
    "            while q:\n",
    "                index = q.pop(0)\n",
    "                for nidx in d[index]:\n",
    "                    if visited[nidx]:\n",
    "                        continue\n",
    "\n",
    "                    cnt += 1\n",
    "                    q.append(nidx)\n",
    "                    visited[nidx] = True\n",
    "            res = max(cnt, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    record:defaultdict[int,int]=defaultdict(lambda:-1)\n",
    "\n",
    "    def isIn(self, xb, yb, rb, x, y) -> bool:\n",
    "        if (pow(xb-x, 2)+pow(yb-y, 2))<= pow(rb, 2):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def dfs(self, bombs: List[List[int]], x, y, r, bombed: list[int], index: int) -> int:\n",
    "        bombed[index] = 1\n",
    "        if index in self.record.keys():\n",
    "            return self.record.get(index)\n",
    "        count = 1\n",
    "        for i in range(0,len(bombed)):\n",
    "            if bombed[i] == 0:\n",
    "                if self.isIn(x,y,r,bombs[i][0],bombs[i][1]):\n",
    "                    # 能引爆\n",
    "                    count+=self.dfs(bombs,bombs[i][0],bombs[i][1],bombs[i][2],bombed,i)\n",
    "\n",
    "        self.record.setdefault(index,count)\n",
    "        return count\n",
    "\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        max_res = 0\n",
    "        i = 0\n",
    "        for x, y, r in bombs:\n",
    "            bombed = [0]*len(bombs)\n",
    "            self.record.clear()\n",
    "            max_res = max(max_res, self.dfs(bombs, x, y, r, bombed, i))\n",
    "            i += 1\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    record:dict[int,int]=dict()\n",
    "\n",
    "    def isIn(self, xb, yb, rb, x, y) -> bool:\n",
    "        if (pow(xb-x, 2)+pow(yb-y, 2))<= pow(rb, 2):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def dfs(self, bombs: List[List[int]], x, y, r, bombed: list[int], index: int) -> int:\n",
    "        bombed[index] = 1\n",
    "        if index in self.record.keys():\n",
    "            return self.record.get(index)\n",
    "        count = 1\n",
    "        for i in range(0,len(bombed)):\n",
    "            if bombed[i] == 0:\n",
    "                if self.isIn(x,y,r,bombs[i][0],bombs[i][1]):\n",
    "                    # 能引爆\n",
    "                    count+=self.dfs(bombs,bombs[i][0],bombs[i][1],bombs[i][2],bombed,i)\n",
    "\n",
    "        self.record.setdefault(index,count)\n",
    "        return count\n",
    "\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        max_res = 0\n",
    "        i = 0\n",
    "        for x, y, r in bombs:\n",
    "            bombed = [0]*len(bombs)\n",
    "            self.record.clear()\n",
    "            max_res = max(max_res, self.dfs(bombs, x, y, r, bombed, i))\n",
    "            i += 1\n",
    "        return max_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        n = len(bombs)\n",
    "        for i in range(n):\n",
    "            x, y, r = bombs[i]\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                x1, y1, r1 = bombs[j]\n",
    "                if (x - x1) * (x - x1) + (y - y1) * (y - y1) <= r * r:\n",
    "                    d[i].append(j)\n",
    "        # print(d)\n",
    "\n",
    "        def dfs(i, vis):\n",
    "            for j in d[i]:\n",
    "                if j not in vis:\n",
    "                    vis.add(j)\n",
    "                    dfs(j, vis)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            vis = {i}\n",
    "            dfs(i, vis)\n",
    "            ans = max(ans, len(vis))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        n = len(bombs)\n",
    "        for i in range(n):\n",
    "            x, y, r = bombs[i]\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                x1, y1, r1 = bombs[j]\n",
    "                if (x - x1) * (x - x1) + (y - y1) * (y - y1) <= r * r:\n",
    "                    d[i].append(j)\n",
    "        # print(d)\n",
    "\n",
    "        def dfs(i, vis):\n",
    "            for j in d[i]:\n",
    "                if j not in vis:\n",
    "                    vis.add(j)\n",
    "                    dfs(j, vis)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            vis = {i}\n",
    "            dfs(i, vis)\n",
    "            ans = max(ans, len(vis))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        d = [0] * (n := len(bombs))\n",
    "        for i, j in product(range(n), repeat = 2):\n",
    "            if dist(bombs[i][:2], bombs[j][:2]) <= bombs[i][2]: d[i] |= (1 << j)\n",
    "        for k, i in product(range(n), repeat = 2):\n",
    "            if (d[i] >> k) & 1: d[i] |= d[k]\n",
    "        return max(d[i].bit_count() for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        n = len(bombs)\n",
    "        # 判断炸弹 u 能否引爆炸弹 v\n",
    "        def isConnected(u: int, v: int) -> bool:\n",
    "            dx = bombs[u][0] - bombs[v][0]\n",
    "            dy = bombs[u][1] - bombs[v][1]\n",
    "            return bombs[u][2] ** 2 >= dx ** 2 + dy ** 2\n",
    "        \n",
    "        # 维护引爆关系有向图\n",
    "        edges = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and isConnected(i, j):\n",
    "                    edges[i].append(j)\n",
    "        res = 0   # 最多引爆数量\n",
    "        for i in range(n):\n",
    "            # 遍历每个炸弹，广度优先搜索计算该炸弹可引爆的数量，并维护最大值\n",
    "            visited = [False] * n\n",
    "            cnt = 1\n",
    "            q = deque([i])\n",
    "            visited[i] = True\n",
    "            while q:\n",
    "                cidx = q.popleft()\n",
    "                for nidx in edges[cidx]:\n",
    "                    if visited[nidx]:\n",
    "                        continue\n",
    "                    cnt += 1\n",
    "                    q.append(nidx)\n",
    "                    visited[nidx] = True\n",
    "            res = max(res, cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        n = len(bombs)\n",
    "        # 判断炸弹 u 能否引爆炸弹 v\n",
    "        def isConnected(u: int, v: int) -> bool:\n",
    "            dx = bombs[u][0] - bombs[v][0]\n",
    "            dy = bombs[u][1] - bombs[v][1]\n",
    "            return bombs[u][2] ** 2 >= dx ** 2 + dy ** 2\n",
    "        \n",
    "        # 维护引爆关系有向图\n",
    "        edges = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and isConnected(i, j):\n",
    "                    edges[i].append(j)\n",
    "        res = 0   # 最多引爆数量\n",
    "        for i in range(n):\n",
    "            # 遍历每个炸弹，广度优先搜索计算该炸弹可引爆的数量，并维护最大值\n",
    "            visited = [False] * n\n",
    "            cnt = 1\n",
    "            q = deque([i])\n",
    "            visited[i] = True\n",
    "            while q:\n",
    "                cidx = q.popleft()\n",
    "                for nidx in edges[cidx]:\n",
    "                    if visited[nidx]:\n",
    "                        continue\n",
    "                    cnt += 1\n",
    "                    q.append(nidx)\n",
    "                    visited[nidx] = True\n",
    "            res = max(res, cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        n=len(bombs)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    if (bombs[i][0]-bombs[j][0])**2+(bombs[i][1]-bombs[j][1])**2<=bombs[i][2]**2:\n",
    "                        g[i].append(j)\n",
    "        ans=[0]\n",
    "        def dfs(x):\n",
    "            res=0\n",
    "            for i in g[x]:\n",
    "                if not vis[i]:\n",
    "                    vis[i]=True\n",
    "                    res+=dfs(i)\n",
    "            return res+1\n",
    "        vis=[False]*n\n",
    "        for i in range(n):\n",
    "            vis=[False]*n\n",
    "            vis[i]=True\n",
    "            ans[0]=max(ans[0],dfs(i))\n",
    "        return ans[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        n=len(bombs)\n",
    "        f=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            #print(f)\n",
    "            for j in range(i+1,n):\n",
    "                d=(bombs[j][0]-bombs[i][0])**2+(bombs[j][1]-bombs[i][1])**2\n",
    "                if bombs[i][2]**2>=d:\n",
    "                    f[i].append(j)\n",
    "                if bombs[j][2]**2>=d:\n",
    "                    f[j].append(i)\n",
    "        res=0\n",
    "        def dfs(start:int)->int:\n",
    "            cnt=1\n",
    "            vis[start]=True\n",
    "            for nex in f[start]:\n",
    "                if not vis[nex]:\n",
    "                    cnt +=dfs(nex)\n",
    "            return cnt\n",
    "        for i in range(n):\n",
    "            vis=[False]*n\n",
    "            res=max(res,dfs(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        n = len(bombs)\n",
    "        for i in range(n-1):\n",
    "            # for j in range(i+1): # WRONG\n",
    "            for j in range(i+1, n):\n",
    "                x1, y1, r1 = bombs[i]\n",
    "                x2, y2, r2 = bombs[j]\n",
    "                d = math.sqrt((x1 - x2)**2 + (y1 - y2)**2)\n",
    "                if d <= r1:\n",
    "                    graph[i].append(j)\n",
    "                if d <= r2:\n",
    "                    graph[j].append(i)\n",
    "\n",
    "        def dfs(node):\n",
    "            if node in visit:\n",
    "                return 0\n",
    "            visit.add(node)\n",
    "            count =1\n",
    "            for nei in graph[node]:\n",
    "                if nei not in visit:\n",
    "                    count += dfs(nei)\n",
    "            return count\n",
    "\n",
    "        res = 0\n",
    "        for node in range(n):\n",
    "            visit = set()\n",
    "            tmp = dfs(node)\n",
    "            # print(len(visit) == tmp) # alternatively, use len(visit)\n",
    "            res = max(res, tmp)\n",
    "        return res\n",
    "\"\"\"\n",
    "n = 3\n",
    "for i in range(n-1):\n",
    "    for j in range(i+1):\n",
    "        print(i, j)\n",
    "print('---')\n",
    "for i in range(n):\n",
    "    for j in range(i+1, n):\n",
    "        print(i, j)\n",
    "0 0\n",
    "1 0\n",
    "1 1\n",
    "---\n",
    "0 1\n",
    "0 2\n",
    "1 2\n",
    "\"\"\"\n",
    "\n",
    "        # def bfs(queue):\n",
    "        #     while queue:\n",
    "        #         node = queue.popleft()\n",
    "        #         for nei in graph[node]:\n",
    "        #             if nei in visited:\n",
    "        #                 continue\n",
    "        #             visited.add(nei)\n",
    "        #             queue.append(nei)\n",
    "\n",
    "        # res = 0\n",
    "        # for node in range(n):\n",
    "        #     visited = set()\n",
    "        #     visited.add(node)\n",
    "        #     queue = collections.deque()\n",
    "        #     queue.append(node)\n",
    "        #     bfs(queue)\n",
    "        #     res = max(res, len(visited))\n",
    "        # return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
